{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #柱状图中最大的矩形"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: largestRectangleArea"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #柱状图中最大的矩形"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定非负整数数组 <code>heights</code>&nbsp;，数组中的数字用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 <code>1</code> 。</p>\n",
    "\n",
    "<p>求在该柱状图中，能够勾勒出来的矩形的最大面积。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/01/04/histogram.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>heights = [2,1,5,6,2,3]\n",
    "<strong>输出：</strong>10\n",
    "<strong>解释：</strong>最大的矩形为图中红色区域，面积为 10\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/01/04/histogram-1.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong> heights = [2,4]\n",
    "<b>输出：</b> 4</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= heights.length &lt;=10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= heights[i] &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 84&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/largest-rectangle-in-histogram/\">https://leetcode-cn.com/problems/largest-rectangle-in-histogram/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [0ynMMM](https://leetcode.cn/problems/0ynMMM/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [0ynMMM](https://leetcode.cn/problems/0ynMMM/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,1,5,6,2,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "\n",
    "        stack = []\n",
    "        res = 0\n",
    "        i = 0\n",
    "        n = len(heights)\n",
    "        while i<n:\n",
    "            if not stack or heights[stack[-1]]<=heights[i]:\n",
    "                stack.append(i)\n",
    "                i += 1\n",
    "            else:\n",
    "                poped = stack.pop()\n",
    "                width = i if not stack else i-stack[-1]-1\n",
    "                res = max(res,width*heights[poped])\n",
    "        while stack:\n",
    "            poped = stack.pop()\n",
    "            width = len(heights) if not stack else i-stack[-1]-1\n",
    "            res = max(res,width*heights[poped])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        stack = []\n",
    "        n = len(heights)\n",
    "        max_area = 0\n",
    "        for i in range(n):\n",
    "            while len(stack) > 0 and heights[stack[-1]] > heights[i]:\n",
    "                idx = stack.pop()\n",
    "                if len(stack) == 0:\n",
    "                    left_idx = -1\n",
    "                else:\n",
    "                    left_idx = stack[-1]\n",
    "                max_area = max(max_area, (i - left_idx - 1) * heights[idx])\n",
    "            stack.append(i)\n",
    "        \n",
    "        while len(stack) > 0:\n",
    "            idx = stack.pop()\n",
    "            if len(stack) == 0:\n",
    "                left_idx = -1\n",
    "            else:\n",
    "                left_idx = stack[-1]\n",
    "            max_area = max(max_area, (n - left_idx - 1) * heights[idx])\n",
    "        return max_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        # 遍历每个元素，将其作为高，然后向左右扩展，记录面积进行比较.\n",
    "        def get_area(indexs,heights):\n",
    "            hi = heights[indexs]\n",
    "\n",
    "            left,right = indexs,indexs\n",
    "            while left>=1:\n",
    "                if heights[left-1]>=hi:\n",
    "                    left -= 1\n",
    "                else:\n",
    "                    break\n",
    "            while right<len(heights)-1:\n",
    "                if heights[right+1]>=hi:\n",
    "                    right += 1\n",
    "                else:\n",
    "                    break\n",
    "            area = (right-left+1)*hi\n",
    "            return area\n",
    "\n",
    "        cnt = 0\n",
    "        for i in range(len(heights)):\n",
    "            if i>0 and heights[i] == heights[i-1]: # 剪枝：相邻元素相等时可以跳过计算.\n",
    "                continue\n",
    "            cnt = max(cnt,get_area(i,heights))\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        max_area = 0\n",
    "        n = len(heights)\n",
    "        for i in range(n):\n",
    "            left = i - 1\n",
    "            right = i + 1\n",
    "            if n * heights[i] > max_area:\n",
    "                while left >= 0 and heights[left] >= heights[i]:\n",
    "                    left -= 1\n",
    "                while right <= n - 1 and heights[right] >= heights[i]:\n",
    "                    right += 1\n",
    "                max_area = max(max_area, (right - left - 1) * heights[i])\n",
    "        return max_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        stackh = [0]\n",
    "        stacki = [-1]\n",
    "        heights.append(0)\n",
    "        res = 0\n",
    "        for i in range(len(heights)):\n",
    "            if heights[i] > stackh[-1]:\n",
    "                stackh.append(heights[i])\n",
    "                stacki.append(i)\n",
    "            elif heights[i] == stackh[-1]:\n",
    "                stacki.pop()\n",
    "                stacki.append(i)\n",
    "            else:\n",
    "                while heights[i] < stackh[-1]:\n",
    "                    left = stacki[-2]\n",
    "                    right = i\n",
    "                    tmp = (right - left -1) * stackh.pop()\n",
    "                    res = max(res, tmp)\n",
    "                    stacki.pop()\n",
    "                if heights[i] > stackh[-1]:\n",
    "                    stacki.append(i)\n",
    "                    stackh.append(heights[i])\n",
    "                if heights[i] == stackh[-1]:\n",
    "                    stacki.pop()\n",
    "                    stacki.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        # 从小到大排序, [h, s, e]\n",
    "        l = []\n",
    "        ret = 0\n",
    "\n",
    "        for i, h in enumerate(heights):\n",
    "            p = bisect.bisect_left(l, [h])\n",
    "            if p == len(l):\n",
    "                l.append([h, i, i + 1])\n",
    "                continue\n",
    "\n",
    "            if l[p][0] == h:\n",
    "                l[p][2] = i + 1\n",
    "                if p + 1 == len(l):\n",
    "                    continue\n",
    "            else:\n",
    "                l.insert(p, [h, i, i + 1])\n",
    "\n",
    "            # 修改p的起始坐标\n",
    "            l[p][1] = min(l[p][1], l[p + 1][1])\n",
    "\n",
    "            # 计算后面面积及删除\n",
    "            e = l[-1][-1]\n",
    "            for i in range(p + 1, len(l)):\n",
    "                ret = max(ret, l[i][0] * (e - l[i][1]))\n",
    "\n",
    "            del l[p + 1:]\n",
    "\n",
    "        # 计算面积\n",
    "        e = l[-1][-1]\n",
    "        for i in range(len(l)):\n",
    "            ret = max(ret, l[i][0] * (e - l[i][1]))\n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        ans = 0\n",
    "        heights.append(0)\n",
    "        heights.insert(0, 0)\n",
    "        stack = []\n",
    "        stack.append(0)\n",
    "\n",
    "        for i in range(1, len(heights)):\n",
    "            if heights[i] > heights[stack[-1]]:\n",
    "                stack.append(i)\n",
    "            elif heights[i] == heights[stack[-1]]:\n",
    "                stack.pop()\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                while len(stack) != 0 and heights[i] < heights[stack[-1]]:\n",
    "                    mid = stack.pop()\n",
    "                    if len(stack) != 0:\n",
    "                        left = stack[-1]\n",
    "                        right = i\n",
    "                        w = right - left - 1\n",
    "                        h = heights[mid]\n",
    "                        ans = max(ans, w * h)\n",
    "                stack.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        stack=[]\n",
    "        n=len(heights)\n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            while len(stack) and heights[i]<heights[stack[-1]]:\n",
    "                index=stack.pop()\n",
    "                height=heights[index]\n",
    "                if len(stack)>0:\n",
    "                    width=i-stack[-1]-1\n",
    "                else:\n",
    "                    width=i\n",
    "                res=max(res, width*height)\n",
    "            stack.append(i)\n",
    "        while len(stack):\n",
    "            index=stack.pop()\n",
    "            height=heights[index]\n",
    "            if len(stack)>0:\n",
    "                width=n-stack[-1]-1\n",
    "            else:\n",
    "                width=n\n",
    "            res=max(res, width*height)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        stack = []        \n",
    "        left, right = [-1] * n, [n] * n\n",
    "        for i, x in enumerate(heights):\n",
    "            while stack and stack[-1][0] >= x:\n",
    "                right[stack[-1][1]] = i\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                left[i] = stack[-1][1]\n",
    "            stack.append((x, i))\n",
    "        return max(heights[i] * (right[i] - left[i] - 1) for i in range(n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        left, right = [0] * n, [n] * n\n",
    "\n",
    "        mono_stack = list()\n",
    "        for i in range(n):\n",
    "            while mono_stack and heights[mono_stack[-1]] >= heights[i]:\n",
    "                right[mono_stack[-1]] = i\n",
    "                mono_stack.pop()\n",
    "            left[i] = mono_stack[-1] if mono_stack else -1\n",
    "            mono_stack.append(i)\n",
    "        \n",
    "        ans = max((right[i] - left[i] - 1) * heights[i] for i in range(n)) if n > 0 else 0\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        left, right = [0] * n, [0] * n\n",
    "\n",
    "        mono_stack = list()\n",
    "        for i in range(n):\n",
    "            while mono_stack and heights[mono_stack[-1]] >= heights[i]:\n",
    "                mono_stack.pop()\n",
    "            left[i] = mono_stack[-1] if mono_stack else -1\n",
    "            mono_stack.append(i)\n",
    "        \n",
    "        mono_stack = list()\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while mono_stack and heights[mono_stack[-1]] >= heights[i]:\n",
    "                mono_stack.pop()\n",
    "            right[i] = mono_stack[-1] if mono_stack else n\n",
    "            mono_stack.append(i)\n",
    "        \n",
    "        ans = max((right[i] - left[i] - 1) * heights[i] for i in range(n)) if n > 0 else 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        stack = []\n",
    "        maxn = 0\n",
    "        length = len(heights)\n",
    "        \n",
    "        heights.append(0)\n",
    "        heights.insert(0, 0)\n",
    "        #print(heights)\n",
    "        for idx in range(length+2):\n",
    "            while stack and (heights[idx] < heights[stack[-1]]):\n",
    "                sum = (idx - stack[-2] - 1)*heights[stack[-1]]\n",
    "                #print(idx, stack[-2], stack[-1], sum)\n",
    "                if sum > maxn:\n",
    "                    maxn = sum\n",
    "                print(maxn)\n",
    "                stack.pop()\n",
    "\n",
    "            stack.append(idx)\n",
    "            #print(heights[idx])\n",
    "\n",
    "        return maxn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        left, right = [0] * n, [0] * n\n",
    "\n",
    "        max_stack = []\n",
    "        for i in range(n):\n",
    "            while max_stack and heights[max_stack[-1]] >= heights[i]:\n",
    "                max_stack.pop()\n",
    "            if max_stack:\n",
    "                left[i] = max_stack[-1]\n",
    "            else:\n",
    "                left[i] = -1\n",
    "            max_stack.append(i)\n",
    "        max_stack.clear()\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while max_stack and heights[max_stack[-1]] >= heights[i]:\n",
    "                max_stack.pop()\n",
    "            if max_stack:\n",
    "                right[i] = max_stack[-1]\n",
    "            else:\n",
    "                right[i] = n\n",
    "            max_stack.append(i)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans, (right[i] - left[i] - 1) * heights[i])\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        left, right =[0] * n, [0] * n\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            while len(stack) > 0 and heights[i] <= heights[stack[-1]]:\n",
    "                stack.pop(-1)\n",
    "            left[i] = -1 if len(stack) == 0 else stack[-1]\n",
    "            stack.append(i)\n",
    "        stack = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while len(stack) > 0 and heights[i] <= heights[stack[-1]]:\n",
    "                stack.pop(-1)\n",
    "            right[i] = n if len(stack) == 0 else stack[-1]\n",
    "            stack.append(i)\n",
    "        area = 0\n",
    "        for i in range(n):\n",
    "            area = max(area, heights[i] * (right[i] - left[i] -  1))\n",
    "        return area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        left, right = [0] * n, [n] * n\n",
    "\n",
    "        max_stack = []\n",
    "        for i in range(n):\n",
    "            while max_stack and heights[max_stack[-1]] >= heights[i]:\n",
    "                right[max_stack[-1]] = i \n",
    "                max_stack.pop()\n",
    "            if max_stack:\n",
    "                left[i] = max_stack[-1]\n",
    "            else:\n",
    "                left[i] = -1\n",
    "            max_stack.append(i)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans, (right[i] - left[i] - 1) * heights[i]) \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        heights.append(0)\n",
    "        n = len(heights)\n",
    "        arr = [-1,0]\n",
    "        res = 0\n",
    "\n",
    "        for i in range(1,n):\n",
    "            if heights[arr[-1]] < heights[i]:\n",
    "                arr.append(i)\n",
    "            else:\n",
    "                while heights[arr[-1]] > heights[i]:\n",
    "                    t = arr.pop()\n",
    "                    res = max(res, heights[t]*(i-arr[-1]-1))\n",
    "                arr.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        st = [-1]\n",
    "        ans = 0\n",
    "        heights.append(0)\n",
    "        for i, h in enumerate(heights):\n",
    "            while len(st) != 1 and heights[st[-1]] > h:\n",
    "                j = st.pop()  # 栈顶（下标）\n",
    "                hj = heights[j]  # 对顶的高度\n",
    "                left = st[-1]  # 刚刚出战的高度往左最远能到的位置\n",
    "                ans = max(ans, hj * (i - left - 1))\n",
    "            st.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        stack = []\n",
    "        heights.append(0)\n",
    "        heights.insert(0, 0)\n",
    "        n, ans = len(heights), 0\n",
    "\n",
    "        for i in range(n):\n",
    "            while stack and heights[i] < heights[stack[-1]]:\n",
    "                mid = stack.pop()\n",
    "                if stack:\n",
    "                    left = stack[-1]\n",
    "                    right = i\n",
    "                    w = right - left - 1\n",
    "                    h = heights[mid]\n",
    "                    ans = max(ans, w * h)\n",
    "            stack.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        stack = []\n",
    "        heights.append(0)\n",
    "        heights.insert(0, 0)\n",
    "        n, ans = len(heights), 0\n",
    "\n",
    "        for i in range(n):\n",
    "            while stack and heights[i] < heights[stack[-1]]:\n",
    "                mid = stack.pop()\n",
    "                if stack:\n",
    "                    right = i\n",
    "                    left = stack[-1]\n",
    "                    w = right - left - 1\n",
    "                    h = heights[mid]\n",
    "                    ans = max(ans, w * h)\n",
    "\n",
    "            stack.append(i)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        left, right = [0] * n, [0] * n\n",
    "\n",
    "        mono_stack = []\n",
    "        for i in range(n):\n",
    "            while mono_stack and heights[mono_stack[-1]] >= heights[i]:\n",
    "                mono_stack.pop()\n",
    "            left[i] = mono_stack[-1] if mono_stack else -1\n",
    "            mono_stack.append(i)\n",
    "        mono_stack = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while mono_stack and heights[mono_stack[-1]] >= heights[i]:\n",
    "                mono_stack.pop()\n",
    "            right[i] = mono_stack[-1] if mono_stack else n\n",
    "            mono_stack.append(i)\n",
    "        ans = max((right[i] - left[i] - 1) * heights[i] for i in range(n))\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        # 单调栈思想\n",
    "        if not heights:\n",
    "            return 0\n",
    "        n = len(heights)\n",
    "        if n==1:\n",
    "            return heights[0]\n",
    "        new_h = [-1 for i in range(n+2)]\n",
    "        for i in range(1,n+1):\n",
    "            new_h[i] = heights[i-1]\n",
    "        r = 0\n",
    "        stack = []\n",
    "        max_area = -float('inf')\n",
    "        while r <= n+1:\n",
    "            while stack and new_h[stack[-1]] > new_h[r]:\n",
    "                p = stack.pop()\n",
    "                l = -1 if not stack else stack[-1]\n",
    "                #l = stack.pop()\n",
    "                area = new_h[p] * (r-l-1)\n",
    "                if area > max_area:\n",
    "                    max_area = area\n",
    "            stack.append(r)\n",
    "            r+=1\n",
    "        return max_area\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        # 单调栈思想\n",
    "        if not heights:\n",
    "            return 0\n",
    "        n = len(heights)\n",
    "        if n==1:\n",
    "            return heights[0]\n",
    "        new_h = [-1 for i in range(n+2)]\n",
    "        for i in range(1,n+1):\n",
    "            new_h[i] = heights[i-1]\n",
    "        r = 0\n",
    "        stack = []\n",
    "        max_area = -float('inf')\n",
    "        while r <= n+1:\n",
    "            while stack and new_h[stack[-1]] > new_h[r]:\n",
    "                p = stack.pop()\n",
    "                l = -1 if not stack else stack[-1]\n",
    "                #l = stack.pop()\n",
    "                area = new_h[p] * (r-l-1)\n",
    "                if area > max_area:\n",
    "                    max_area = area\n",
    "            stack.append(r)\n",
    "            r+=1\n",
    "        return max_area\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        left = [-1]*n\n",
    "        right = [n]*n\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            while stack and heights[stack[-1]] > heights[i]:\n",
    "                right[stack.pop()] = i\n",
    "            if stack:\n",
    "                left[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans, heights[i]*(right[i]-left[i]-1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        #两次循环找出左右边界即可\n",
    "        #以左侧边界为例，如果左侧值比当前值高，那么当前值的左侧边界就是左侧值的左侧边界，反之就是自己\n",
    "        #最左边的左侧边界只能是自己\n",
    "        #右侧则是一样\n",
    "        left = [-1]\n",
    "        stack = [0]\n",
    "        for i in range(1,len(heights)):\n",
    "            while stack and heights[i] <= heights[stack[-1]]:\n",
    "                stack.pop()\n",
    "            if not stack:\n",
    "                left.append(-1)\n",
    "            else:\n",
    "                left.append(stack[-1])\n",
    "            stack.append(i)\n",
    "        right = [len(heights)]\n",
    "        stack = [len(heights)-1]\n",
    "        for i in range(1,len(heights)):\n",
    "            i = len(heights)-1-i\n",
    "            while stack and heights[i] <= heights[stack[-1]]:\n",
    "                stack.pop()\n",
    "            if not stack:\n",
    "                right.append(len(heights))\n",
    "            else:\n",
    "                right.append(stack[-1])\n",
    "            stack.append(i)\n",
    "        right = right[::-1]\n",
    "        max1 = 0\n",
    "        for i in range(len(left)):\n",
    "            if (right[i] - left[i] - 1) * heights[i] > max1:\n",
    "                max1 = (right[i] - left[i] - 1) * heights[i]\n",
    "        return max1\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        left, right =[0] * n, [0] * n\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            while len(stack) > 0 and heights[i] <= heights[stack[-1]]:\n",
    "                stack.pop(-1)\n",
    "            left[i] = -1 if len(stack) == 0 else stack[-1]\n",
    "            stack.append(i)\n",
    "        stack = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while len(stack) > 0 and heights[i] <= heights[stack[-1]]:\n",
    "                stack.pop(-1)\n",
    "            right[i] = n if len(stack) == 0 else stack[-1]\n",
    "            stack.append(i)\n",
    "        area = 0\n",
    "        for i in range(n):\n",
    "            area = max(area, heights[i] * (right[i] - left[i] -  1))\n",
    "            print(i, left[i], right[i])\n",
    "        return area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "\n",
    "        n=len(heights)\n",
    "        heights=[-1]+heights+[-1]\n",
    "        print(heights)\n",
    "        stack=[]\n",
    "        res=[]\n",
    "        for i in range(n+2):\n",
    "            while stack and heights[stack[-1]]>heights[i]:\n",
    "                k=stack.pop()\n",
    "                h=heights[k]\n",
    "                wide=i-stack[-1]-1\n",
    "                s=wide*h\n",
    "                res.append(s)\n",
    "            stack.append(i)\n",
    "        return(max(res))\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        def min_lr(heights):\n",
    "            q=[]\n",
    "            a1=[]\n",
    "            for i in range(len(heights)):\n",
    "                while q and heights[q[-1]]>=heights[i]:\n",
    "                    q.pop()\n",
    "                # print(i,q)\n",
    "                a1.append(q[-1] if q else -1)\n",
    "                q.append(i)\n",
    "            return a1\n",
    "        a1 = min_lr(heights)\n",
    "        a2 = min_lr(heights[::-1])[::-1]\n",
    "\n",
    "        print(a1)\n",
    "        print(a2)\n",
    "        maxi=0\n",
    "        for i in range(len(heights)):\n",
    "            maxi=max(maxi, (len(heights)-a1[i]-a2[i]-2)*heights[i] )\n",
    "        return maxi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        boundl, boundr = [-1] * len(heights), [len(heights)] * len(heights)\n",
    "        \n",
    "        stack = []\n",
    "        for i in range(len(heights)):\n",
    "            while len(stack) > 0 and stack[-1][0] >= heights[i]:\n",
    "                boundr[stack.pop()[1]] = i\n",
    "            if len(stack) != 0:\n",
    "                boundl[i] = stack[-1][1]\n",
    "            stack.append((heights[i], i))\n",
    "        \n",
    "        # stack = []\n",
    "        # for i in range(len(heights) - 1, -1, -1):\n",
    "        #     while len(stack) > 0 and stack[-1][0] >= heights[i]:\n",
    "        #         stack.pop()\n",
    "        #     if len(stack) != 0:\n",
    "        #         boundr[i] = stack[-1][1]\n",
    "        #     stack.append((heights[i], i))\n",
    "        \n",
    "        print(boundl, boundr)\n",
    "        # [-1, -1, 1, 2, 1, 4] [1, 6, 4, 4, 6, 6]\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(len(heights)):\n",
    "            l = i - boundl[i] - 1\n",
    "            r = boundr[i] - i - 1\n",
    "            res = max(res, (l + r + 1) * heights[i])\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        def min_lr(heights):\n",
    "            q=[]\n",
    "            a1=[]\n",
    "            for i in range(len(heights)):\n",
    "                while q and heights[q[-1]]>=heights[i]:\n",
    "                    q.pop()\n",
    "                # print(i,q)\n",
    "                a1.append(q[-1] if q else -1)\n",
    "                q.append(i)\n",
    "            return a1\n",
    "        a1 = min_lr(heights)\n",
    "        a2 = min_lr(heights[::-1])[::-1]\n",
    "\n",
    "        # print(a1)\n",
    "        # print(a2)\n",
    "        maxi=0\n",
    "        for i in range(len(heights)):\n",
    "            maxi=max(maxi, (len(heights)-a1[i]-a2[i]-2)*heights[i] )\n",
    "        return maxi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        # 暴力超时\n",
    "        # n = len(heights)\n",
    "        # ans = 0\n",
    "        # for mid in range(n):  # 枚举中点\n",
    "        #     left, right = mid, mid\n",
    "        #     while left > 0 and heights[left-1] >= heights[mid]:\n",
    "        #         left -= 1\n",
    "        #     while right < n-1 and heights[mid] <= heights[right+1]:\n",
    "        #         right += 1\n",
    "        #     ans = max(ans, (right - left + 1) * heights[mid])\n",
    "        # return ans\n",
    "\n",
    "        # 暴力超时\n",
    "        # n = len(heights)\n",
    "        # ans = 0\n",
    "        # for left in range(n):\n",
    "        #     minHeight = float('inf')\n",
    "        #     for right in range(left, n):\n",
    "        #         minHeight = min(minHeight, heights[right])\n",
    "        #         ans = max(ans, (right - left + 1) * minHeight)\n",
    "        # return ans\n",
    "\n",
    "        n = len(heights)\n",
    "        left_index, right_index = [0] * n, [0] * n\n",
    "\n",
    "        my_stack = []\n",
    "        for i in range(n):\n",
    "            while len(my_stack) > 0 and heights[my_stack[-1]] >= heights[i]:\n",
    "                my_stack.pop()\n",
    "            left_index[i] = my_stack[-1] if len(my_stack)!= 0 else -1\n",
    "            my_stack.append(i)\n",
    "        \n",
    "        my_stack = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while len(my_stack) > 0 and heights[my_stack[-1]] >= heights[i]:\n",
    "                my_stack.pop()\n",
    "            right_index[i] = my_stack[-1] if len(my_stack)!= 0 else n\n",
    "            my_stack.append(i)\n",
    "        \n",
    "        print(left_index)\n",
    "        print(right_index)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            # if n > 0:\n",
    "            ans = max(ans, (right_index[i] - left_index[i] - 1) * heights[i])\n",
    "            # else:\n",
    "            #     ans = 0\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        heights = [-1] + heights + [0]\n",
    "        stack = []\n",
    "        length = len(heights)\n",
    "        ans = [0] * length\n",
    "\n",
    "        for i,height in enumerate(heights):\n",
    "            while stack and heights[stack[-1]] > height:\n",
    "                ans[stack[-1]] = heights[stack[-1]] * (i-1-stack[-2])\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        return max(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        stack = []        \n",
    "        left, right = [-1] * n, [n] * n\n",
    "        for i, x in enumerate(heights):\n",
    "            while stack and stack[-1][0] >= x:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                left[i] = stack[-1][1]\n",
    "            stack.append((x, i))\n",
    "        stack = []\n",
    "        for i, x in enumerate(reversed(heights)):\n",
    "            while stack and stack[-1][0] >= x:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                right[n - 1 - i] = n - 1 - stack[-1][1]\n",
    "            stack.append((x, i))\n",
    "        return max(heights[i] * (right[i] - left[i] - 1) for i in range(n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        left,right = [0]*n,[0]*n\n",
    "        \n",
    "        momo_stack = list()\n",
    "        for i in range(n):\n",
    "            while momo_stack and heights[momo_stack[-1]] >= heights[i]:\n",
    "                momo_stack.pop()\n",
    "            left[i] = momo_stack[-1] if momo_stack else -1\n",
    "            momo_stack.append(i)\n",
    "\n",
    "        momo_stack = list()\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while momo_stack and heights[momo_stack[-1]] >= heights[i]:\n",
    "                momo_stack.pop()\n",
    "            right[i] = momo_stack[-1] if momo_stack else n\n",
    "            momo_stack.append(i)\n",
    "        \n",
    "        print(left,right)\n",
    "        ans = max((right[i]-left[i]-1)*heights[i] for i in range(n)) if n > 0 else 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        #两次循环找出左右边界即可\n",
    "        #以左侧边界为例，如果左侧值比当前值高，那么当前值的左侧边界就是左侧值的左侧边界，反之就是自己\n",
    "        #最左边的左侧边界只能是自己\n",
    "        #右侧则是一样\n",
    "        left = [-1]\n",
    "        stack = [0]\n",
    "        for i in range(1,len(heights)):\n",
    "            while stack and heights[i] <= heights[stack[-1]]:\n",
    "                stack.pop()\n",
    "            if not stack:\n",
    "                left.append(-1)\n",
    "            else:\n",
    "                left.append(stack[-1])\n",
    "            stack.append(i)\n",
    "        right = [len(heights)]\n",
    "        stack = [len(heights)-1]\n",
    "        for i in range(1,len(heights)):\n",
    "            i = len(heights)-1-i\n",
    "            while stack and heights[i] <= heights[stack[-1]]:\n",
    "                stack.pop()\n",
    "            if not stack:\n",
    "                right.append(len(heights))\n",
    "            else:\n",
    "                right.append(stack[-1])\n",
    "            stack.append(i)\n",
    "        right = right[::-1]\n",
    "        print(left,right)\n",
    "        max1 = 0\n",
    "        for i in range(len(left)):\n",
    "            if (right[i] - left[i] - 1) * heights[i] > max1:\n",
    "                max1 = (right[i] - left[i] - 1) * heights[i]\n",
    "        return max1\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import *\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        ans = 0\n",
    "        g = defaultdict(list)\n",
    "        n = len(heights)\n",
    "        sl = SortedList()\n",
    "        for i, x in enumerate(heights): g[x].append(i)\n",
    "        for x in sorted(set(heights)):\n",
    "            for i in g[x]:\n",
    "                p = sl.bisect_left(i)-1\n",
    "                l = sl[p] if 0 <= p < len(sl) else -1\n",
    "                p = sl.bisect_left(i)\n",
    "                r = sl[p] if 0 <= p < len(sl) else n\n",
    "                ans = max(ans, (r-l - 1) * x)\n",
    "            for i in g[x]: sl.add(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "\n",
    "\n",
    "        n = len(heights)\n",
    "        left, right =[0]* len(heights),[0] * len(heights)\n",
    "\n",
    "        ## 利用单调栈 求出 每个 柱子 左边 右边的 短板\n",
    "\n",
    "        mono_stack = []\n",
    "        mono_stack.append(0)\n",
    "\n",
    "        left[0] = -1\n",
    "\n",
    "        for i in range(1,len(heights)):\n",
    "            while mono_stack and  heights[i] <= heights[mono_stack[-1]]:\n",
    "                mono_stack.pop()\n",
    "\n",
    "            if not mono_stack:\n",
    "                left[i] = -1 \n",
    "            else:\n",
    "                left[i] = mono_stack[-1]\n",
    "            mono_stack.append(i)\n",
    "\n",
    "        mono_stack = []\n",
    "\n",
    "        mono_stack.append(len(heights) -1)\n",
    "        right[len(heights) - 1] = len(heights)\n",
    "\n",
    "        for i in range(len(heights)-2, -1, -1):\n",
    "            \n",
    "            while mono_stack and heights[i] <= heights[mono_stack[-1]]:\n",
    "                mono_stack.pop()\n",
    "\n",
    "            if not mono_stack:\n",
    "                right[i] = len(heights)\n",
    "            else:\n",
    "                right[i] = mono_stack[-1]\n",
    "            mono_stack.append(i)\n",
    "        print(left,right)\n",
    "        max_res = 0\n",
    "        for i in range(len(heights)):\n",
    "            if max_res < (right[i] - left[i] -1)*heights[i]:\n",
    "                max_res  = (right[i] - left[i] -1)*heights[i]\n",
    "\n",
    "        return max_res\n",
    "        \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        stack = [(0, -1)]\n",
    "        heights.append(0)\n",
    "        res = 0\n",
    "        for i,height in enumerate(heights):\n",
    "            while stack and height < stack[-1][0]:\n",
    "                h = stack[-1][0]            # 长\n",
    "                w = i - stack[-2][1] - 1    # 宽\n",
    "                res = max(res, h*w)\n",
    "                stack.pop()                 # 栈顶元素已经求过面积，pop出来，换下一个元素\n",
    "            stack.append((height, i))       # 和栈顶元素比较之后，当前元素才可以入栈\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "\n",
    "        #if None\n",
    "        if not heights:\n",
    "            return 0\n",
    "\n",
    "        #init\n",
    "        res = 0\n",
    "        stack = [(0,-1)] #(init_height, inx)\n",
    "        heights.append(0)\n",
    "\n",
    "        #do traverse\n",
    "        for inx, hgt in enumerate(heights):\n",
    "            while stack:\n",
    "                top_elem_hgt = stack[-1][0]\n",
    "                # print('top_elem_hgt:\\t', top_elem_hgt)\n",
    "                if hgt >= top_elem_hgt:\n",
    "                    stack.append((hgt, inx))\n",
    "                    break\n",
    "                else:\n",
    "                    # print('stack:\\t', stack)\n",
    "                    # print('hgt:\\t', hgt)\n",
    "                    flag_inx = stack[-2][1]\n",
    "                    top_elem_hgt, top_inx = stack.pop()\n",
    "                    width = inx - flag_inx - 1\n",
    "                    # print('*******', inx, '*******')\n",
    "                    # print('top_elem_hgt:\\t', top_elem_hgt)\n",
    "                    # print('width:\\t', width)\n",
    "                    cur_area = (top_elem_hgt) * width\n",
    "                    # print('cur_area:\\t', cur_area)\n",
    "                    res = max(res, cur_area)\n",
    "            # print('stack:\\t', stack)\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "#         stack = [(0, -1)]\n",
    "#         heights.append(0)\n",
    "#         res = 0\n",
    "#         for i,height in enumerate(heights):\n",
    "#             while stack and height < stack[-1][0]:\n",
    "#                 h = stack[-1][0]            # 长\n",
    "#                 w = i - stack[-2][1] - 1    # 宽\n",
    "#                 print('*******', i, '*******')\n",
    "#                 print('hgt:\\t', h)\n",
    "#                 print('width:\\t', w)\n",
    "#                 res = max(res, h*w)\n",
    "#                 stack.pop()                 # 栈顶元素已经求过面积，pop出来，换下一个元素\n",
    "#                 print('res:\\t', res)\n",
    "#             stack.append((height, i))       # 和栈顶元素比较之后，当前元素才可以入栈\n",
    "#         return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        stack = [-1]\n",
    "        n = len(heights)\n",
    "        Area = 0\n",
    "        for i in range(n):\n",
    "            while len(stack)>1 and heights[stack[-1]] > heights[i]:\n",
    "                \n",
    "                Area = max(Area,heights[stack[-1]]*(i-stack[-2]-1))\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        Area = max(Area,max([heights[stack[i]]*(n-stack[i-1]-1) for i in range(1,len(stack))]))\n",
    "               \n",
    "        return Area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        stack = [(0, -1)]\n",
    "        heights.append(0)\n",
    "        res = 0\n",
    "        for i, height in enumerate(heights):\n",
    "            while stack and height < stack[-1][0]:\n",
    "                h = stack[-1][0] #高\n",
    "                w = i - stack[-2][1] - 1 #宽\n",
    "                res = max(res, h * w)\n",
    "                stack.pop () # 栈顶元素已经求过面积，pop出来，换下一个元素\n",
    "            stack.append((height,i))  # 和栈顶元素比较之后，当前元素才可以入栈\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n=len(heights)\n",
    "        left,right=[-1]*n,[n]*n\n",
    "        st=[]\n",
    "        for i in range(n):\n",
    "            while st and heights[st[-1]]>=heights[i]:\n",
    "                right[st[-1]]=i\n",
    "                st.pop()\n",
    "            if st:\n",
    "                left[i]=st[-1]\n",
    "            st.append(i)\n",
    "        return max([(right[i]-left[i]-1)*heights[i] for i in range(n)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        l = [-1] * n\n",
    "        r = [n] * n\n",
    "        s = []\n",
    "        for i in range(n):\n",
    "            while s and heights[s[-1]] > heights[i]:\n",
    "                idx = s.pop()\n",
    "                r[idx] = i\n",
    "            s.append(i)\n",
    "        \n",
    "        s = []\n",
    "        heights_reverse = heights[::-1]\n",
    "        for i in range(n):\n",
    "            while s and heights_reverse[s[-1]] > heights_reverse[i]:\n",
    "                idx = s.pop()\n",
    "                l[n-1-idx] = n-1-i\n",
    "            s.append(i)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            temp = heights[i]*(r[i]-l[i]-1)\n",
    "            res = max(res, temp)\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        left = [0]*len(heights)\n",
    "        right = [0] *len(heights)\n",
    "\n",
    "        left_stack = []\n",
    "        j = 0\n",
    "        for i in range(1000000):\n",
    "            if left_stack:\n",
    "                if heights[j] > heights[left_stack[-1]]:\n",
    "                    left[j] = j - left_stack[-1] - 1\n",
    "                    left_stack.append(j)\n",
    "                    j += 1\n",
    "                else:\n",
    "                    left_stack.pop()\n",
    "            else:\n",
    "                left[j] = j\n",
    "                left_stack.append(j)\n",
    "                j += 1\n",
    "            if j == len(heights):\n",
    "                break\n",
    "\n",
    "        right_stack = []\n",
    "        j = len(heights)-1\n",
    "        for i in range(1000000):\n",
    "            if right_stack:\n",
    "                if heights[j] > heights[right_stack[-1]]:\n",
    "                    right[j] = right_stack[-1] - j - 1\n",
    "                    right_stack.append(j)\n",
    "                    j -= 1\n",
    "                else:\n",
    "                    right_stack.pop()\n",
    "            else:\n",
    "                right[j] = len(heights)-1 - j\n",
    "                right_stack.append(j)\n",
    "                j -= 1\n",
    "            if j == -1:\n",
    "                break\n",
    "        \n",
    "        maxi = 0\n",
    "        for i in range(len(heights)):\n",
    "            aa = heights[i] * (1+left[i]+right[i])\n",
    "            maxi = max(maxi, aa)\n",
    "\n",
    "        return maxi    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        max_v = 0\n",
    "        def f(h):\n",
    "            a = [-1 for _ in range(len(h))]\n",
    "            stack = []\n",
    "            for i in range(len(h)):\n",
    "                if len(stack) == 0:\n",
    "                    stack.append(i)\n",
    "                    continue\n",
    "                if h[i] > h[stack[-1]]:\n",
    "                    stack.append(i)\n",
    "                else:\n",
    "                    while len(stack)!= 0 and h[i] <= h[stack[-1]]:\n",
    "                        a[stack[-1]] = stack[-2] if len(stack) >= 2 else -1\n",
    "                        del stack[-1]\n",
    "                    stack.append(i)\n",
    "            return a[:-1]\n",
    "        heights.append(-1)\n",
    "        a = f(heights)\n",
    "        del heights[-1]\n",
    "        heights = heights[::-1]\n",
    "        heights.append(-1)\n",
    "        b = [len(heights)-1-item - 1 for item in f(heights)[::-1]]\n",
    "        print(a,b)\n",
    "        del heights[-1]\n",
    "        heights = heights[::-1]\n",
    "        for i in range(len(a)):\n",
    "            tmp = (b[i]-a[i]-1)*heights[i]\n",
    "            if tmp > max_v:\n",
    "                max_v = tmp\n",
    "        return max_v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        left, right = [0] * n, [n] * n\n",
    "\n",
    "        mono_stack = list()\n",
    "        \n",
    "        for i in range(n):\n",
    "            while mono_stack and heights[mono_stack[-1]]>=heights[i]:\n",
    "                right[mono_stack[-1]] = i\n",
    "                mono_stack.pop()\n",
    "            left[i] = mono_stack[-1] if mono_stack else -1\n",
    "            mono_stack.append(i)\n",
    "        ans = [(right[i]-1-left[i])*heights[i] for i in range(n)]\n",
    "        return max(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        # 对于每个idx，要找到以他为最短板可以左右衍生多少\n",
    "        # 单调栈，保存最小的\n",
    "        stack = [[-1,-1]]\n",
    "        n = len(heights)\n",
    "        left = [0] * n\n",
    "        for i in range(n):\n",
    "            while stack:\n",
    "                if heights[i] <= stack[-1][0]:\n",
    "                    stack.pop()\n",
    "                else:\n",
    "                    break\n",
    "            # print(heights[i],stack)\n",
    "            left[i] = i - stack[-1][1] - 1\n",
    "            stack.append([heights[i], i])\n",
    "        right = [0] * n\n",
    "        stack = [[-1,n]]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while heights[i] <= stack[-1][0]:\n",
    "                stack.pop()\n",
    "            right[i] = stack[-1][1] - i - 1\n",
    "            stack.append([heights[i],i])\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans, heights[i] * (1 + left[i] + right[i]))\n",
    "                \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        if(n==0):\n",
    "            return 0\n",
    "        elif(n==1):\n",
    "            return heights[0]\n",
    "        left, right = [0]*n, [0]*n\n",
    "        min_stack = []\n",
    "        for i in range(n):\n",
    "            while(min_stack and heights[min_stack[-1]] >= heights[i]):\n",
    "                min_stack.pop()\n",
    "            left[i] = min_stack[-1] if min_stack else -1\n",
    "            min_stack.append(i)\n",
    "        min_stack = []\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while(min_stack and heights[min_stack[-1]] >= heights[i]):\n",
    "                min_stack.pop()\n",
    "            right[i] = min_stack[-1] if min_stack else n\n",
    "            min_stack.append(i)\n",
    "            \n",
    "        return max([(right[i]-1-left[i]) * heights[i] for i in range(n)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        left = [0] * n\n",
    "        right = [0] * n\n",
    "\n",
    "        mono_stack = []\n",
    "        for i in range(n):\n",
    "            while mono_stack and heights[mono_stack[-1]] >= heights[i]:\n",
    "                mono_stack.pop()\n",
    "            left[i] = mono_stack[-1] if mono_stack else -1\n",
    "            mono_stack.append(i)\n",
    "        \n",
    "        mono_stack = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while mono_stack and heights[mono_stack[-1]] >= heights[i]:\n",
    "                mono_stack.pop()\n",
    "            right[i] = mono_stack[-1] if mono_stack else n\n",
    "            mono_stack.append(i)\n",
    "        \n",
    "        return max([(right[i]-left[i]-1) * heights[i] for i in range(n)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        left = [0] * n\n",
    "        right = [0] * n\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            while stack and heights[stack[-1]] >= heights[i]:\n",
    "                stack.pop()\n",
    "            left[i] = stack[-1] if stack else -1\n",
    "            stack.append(i)\n",
    "        stack = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while stack and heights[stack[-1]] >= heights[i]:\n",
    "                stack.pop()\n",
    "            right[i] = stack[-1] if stack else n\n",
    "            stack.append(i)\n",
    "        return max([(right[i]-left[i]-1) * heights[i] for i in range(n)])\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        st = []\n",
    "        left, right = [0] * n, [0] * n\n",
    "        \n",
    "        for idx in range(n):\n",
    "            while st and heights[st[-1]] >= heights[idx]:\n",
    "                # st_l[st[-1]] = idx\n",
    "                st.pop()\n",
    "                \n",
    "            if not st:\n",
    "                left[idx] = -1\n",
    "            else: \n",
    "                left[idx] = st[-1]\n",
    "            st.append(idx)\n",
    "\n",
    "        st = []\n",
    "        for idx in range(n - 1, -1, -1):\n",
    "            while st and heights[st[-1]] >= heights[idx]:\n",
    "                # st_l[st[-1]] = idx\n",
    "                st.pop()\n",
    "                \n",
    "            if not st:\n",
    "                right[idx] = n\n",
    "            else: \n",
    "                right[idx] = st[-1]\n",
    "            st.append(idx)\n",
    "        # print(left, right)\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            # print(right, left)\n",
    "            ans.append(heights[i] * (right[i] - left[i] - 1))\n",
    "\n",
    "        return max(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        stack = []\n",
    "        left, right = [0] * n, [n] * n\n",
    "\n",
    "        for i in range(n):\n",
    "            while stack and heights[stack[-1]] >= heights[i]:\n",
    "                right[stack[-1]] = i\n",
    "                stack.pop()\n",
    "            left[i] = stack[-1] if stack else -1\n",
    "            stack.append(i)\n",
    "        return max([(right[i] - left[i]-1) * heights[i] for i in range(n)]) if n > 0 else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        st = [[-1,-1]]\n",
    "        heights.append(0)\n",
    "        res = 0\n",
    "        for i,h in enumerate(heights):\n",
    "            while st and h < st[-1][0]:\n",
    "                he = st.pop()[0]\n",
    "                we = st[-1][1]\n",
    "                res = max(res,he * (i - we - 1))\n",
    "            st.append([h,i])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "\n",
    "#         maxx,n=0,len(heights)\n",
    "#         if len(set(heights))==1:\n",
    "#             return heights[0]*n\n",
    "#         for i in range(n):\n",
    "#             l,r=0,0\n",
    "#             for j in range(i-1,-1,-1):\n",
    "#                 if heights[j]<heights[i]:\n",
    "#                     break\n",
    "#                 l+=1\n",
    "#             for k in range(i+1,n):\n",
    "#                 if heights[k]<heights[i]:\n",
    "#                     break\n",
    "#                 r+=1\n",
    "#             maxx=max(maxx,heights[i]*(l+r+1))\n",
    "#         return maxx\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, h: List[int]) -> int:\n",
    "        stk = []\n",
    "        n = len(h)\n",
    "        left = [0 for i in range(n)]\n",
    "        right = [0 for i in range(n)]\n",
    "        \n",
    "        for i in range(n):\n",
    "            while len(stk) > 0 and h[stk[-1]] >= h[i]:\n",
    "                stk.pop()\n",
    "            if len(stk) == 0:\n",
    "                left[i] = 0 \n",
    "            else:\n",
    "                left[i] = stk[-1] + 1\n",
    "            stk.append(i) \n",
    "\n",
    "        stk = [] \n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while len(stk) > 0 and h[stk[-1]] >= h[i]:\n",
    "                stk.pop()\n",
    "            if len(stk) == 0:\n",
    "                right[i] = n + 1\n",
    "            else:\n",
    "                right[i] = stk[-1] + 1\n",
    "            stk.append(i)\n",
    "\n",
    "        ans = -2**31\n",
    "        for i in range(n):\n",
    "            ans = max(ans, h[i] * (right[i] - left[i] - 1))\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        # 左边比我小的最远位置, 向前遍历\n",
    "        leftStk = []\n",
    "        leftLT = [-1] * n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            h = heights[i]\n",
    "            while leftStk and h < heights[leftStk[-1]]:\n",
    "                idx = leftStk.pop()\n",
    "                leftLT[idx] = i\n",
    "            leftStk.append(i)\n",
    "\n",
    "        # 右边比我小的最远位置, 向后遍历\n",
    "        rightStk = []\n",
    "        rightLT = [n] * n\n",
    "        for i in range(n):\n",
    "            h = heights[i]\n",
    "            while rightStk and h < heights[rightStk[-1]]:\n",
    "                idx = rightStk.pop()\n",
    "                rightLT[idx] = i\n",
    "            rightStk.append(i)\n",
    "\n",
    "        maxArea = 0\n",
    "        curArea = 0\n",
    "        for i in range(n):\n",
    "            curArea = heights[i] * (rightLT[i] - leftLT[i] - 1)\n",
    "            maxArea = max(maxArea, curArea)\n",
    "        return maxArea"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Data:\n",
    "    def __init__(self, idx, height):\n",
    "        self.idx = idx\n",
    "        self.height = height\n",
    "\n",
    "class Stack:\n",
    "    def __init__(self):\n",
    "        self.data = []\n",
    "        self.end_idx = -1\n",
    "\n",
    "    def clean(self):\n",
    "        self.data = []\n",
    "        self.end_idx = -1\n",
    "\n",
    "    def pop(self):\n",
    "        if self.end_idx >= 0:\n",
    "            self.end_idx = self.end_idx - 1\n",
    "            return self.data[self.end_idx + 1]\n",
    "        else:\n",
    "            return None\n",
    "        \n",
    "    def push(self, data):\n",
    "        self.end_idx = self.end_idx + 1\n",
    "        if len(self.data) - 1 >= self.end_idx:\n",
    "            self.data[self.end_idx] = data\n",
    "        else:\n",
    "            self.data.append(data)\n",
    "\n",
    "    def top(self):\n",
    "        if self.end_idx >= 0:\n",
    "            return self.data[self.end_idx]\n",
    "        else:\n",
    "            return None\n",
    "\n",
    "    def size(self):\n",
    "        return self.end_idx + 1\n",
    "\n",
    "\n",
    "def check(ss, idx, h):\n",
    "    if ss.size() == 0:\n",
    "        ss.push(Data(idx, h))\n",
    "        return ss, -1\n",
    "    elif ss.top().height < h:\n",
    "        out_idx = ss.top().idx\n",
    "        ss.push(Data(idx, h))\n",
    "        return ss, out_idx\n",
    "    else:\n",
    "        ss.pop()\n",
    "        return check(ss, idx, h)\n",
    "    \n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "\n",
    "        ss = Stack()\n",
    "        left = [-1 for i in range(len(heights))]\n",
    "        for i in range(len(heights)):\n",
    "            ss, left[i] = check(ss, i, heights[i])\n",
    "            # for ii in range(ss.end_idx):\n",
    "            #     print(ss.data[ii].height, ss.data[ii].idx)\n",
    "            # print()\n",
    "        \n",
    "        ss = Stack()\n",
    "        right = [-1 for i in range(len(heights))]\n",
    "        for i in range(len(heights)-1, -1, -1):\n",
    "            ss, right[i] = check(ss, i, heights[i])\n",
    "            if right[i] < 0:\n",
    "                right[i] = len(heights)\n",
    "\n",
    "        area = [heights[i] * (right[i] - left[i] - 1) for i in range(len(heights))]\n",
    "\n",
    "        max_area = 0\n",
    "        for i in range(len(heights)):\n",
    "            max_area = max(max_area, area[i])\n",
    "\n",
    "        # print(left)\n",
    "        # print(right)\n",
    "        # print(area)\n",
    "\n",
    "        return max_area\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        left=[0]*len(heights)\n",
    "        right=[0]*len(heights)\n",
    "        stack=[]\n",
    "        for i in range(len(heights)):\n",
    "            while stack and heights[stack[-1]]>=heights[i]:\n",
    "                stack.pop()\n",
    "            left[i]=stack[-1] if stack else -1\n",
    "            stack.append(i)\n",
    "        stack=[]\n",
    "        for j in range(len(heights)-1,-1,-1):\n",
    "            while stack and heights[stack[-1]]>=heights[j]:\n",
    "                stack.pop()\n",
    "            right[j]=stack[-1] if stack else len(heights)\n",
    "            stack.append(j)\n",
    "        return max([(right[i]-left[i]-1)*heights[i] for i in range(len(heights))])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        left,right = [],[]\n",
    "        stack = [-1]\n",
    "        n = len(heights)\n",
    "        for i in range(n):\n",
    "            while len(stack)>1 and heights[stack[-1]] >= heights[i]:\n",
    "                stack.pop()\n",
    "            left.append(stack[-1])\n",
    "            stack.append(i)\n",
    "        stack1 = [n]\n",
    "        for j in range(n-1,-1,-1):\n",
    "            while len(stack1)>1 and heights[stack1[-1]] >= heights[j]:\n",
    "                stack1.pop()\n",
    "            right.append(stack1[-1])\n",
    "            stack1.append(j)\n",
    "        \n",
    "        Area = [(right[n-i-1]-left[i]-1)*heights[i] for i in range(n)]\n",
    "\n",
    "\n",
    "        \n",
    "        return max(Area)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        left,right = [],[]\n",
    "        stack = [-1]\n",
    "        n = len(heights)\n",
    "        for i in range(n):\n",
    "            while len(stack)>1 and heights[stack[-1]] >= heights[i]:\n",
    "                stack.pop()\n",
    "            left.append(stack[-1])\n",
    "            stack.append(i)\n",
    "        stack1 = [n]\n",
    "        for j in range(n-1,-1,-1):\n",
    "            while len(stack1)>1 and heights[stack1[-1]] >= heights[j]:\n",
    "                stack1.pop()\n",
    "            right.append(stack1[-1])\n",
    "            stack1.append(j)\n",
    "        \n",
    "        Area = [(right[n-i-1]-left[i]-1)*heights[i] for i in range(n)]\n",
    "\n",
    "\n",
    "        \n",
    "        return max(Area)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        stack = []\n",
    "        left = []\n",
    "        for i in range(n):\n",
    "            while stack and heights[stack[-1]]>=heights[i]:\n",
    "                stack.pop()\n",
    "            if len(stack) == 0:\n",
    "                left.append(-1)\n",
    "            else:\n",
    "                left.append(stack[-1])\n",
    "            stack.append(i)\n",
    "        stack = []\n",
    "        right = []\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while stack and heights[stack[-1]] >= heights[i]:\n",
    "                stack.pop()\n",
    "            if len(stack) == 0:\n",
    "                right.insert(0,n)\n",
    "            else:\n",
    "                right.insert(0,stack[-1])\n",
    "            stack.append(i)\n",
    "        res_list = [(right[i]-left[i]-1)*heights[i] for i in range(n)]\n",
    "        # print(left)\n",
    "        # print(right)\n",
    "        # print(res_list)\n",
    "        res = max(res_list)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n=len(heights)\n",
    "        stack=[0]\n",
    "        left=[-1]*n\n",
    "        right=[n]*n\n",
    "        for i in range(1,n):\n",
    "            while stack and heights[stack[-1]]>heights[i]:\n",
    "                right[stack.pop()]=i\n",
    "            if stack:\n",
    "                left[i]=stack[-1]    \n",
    "            stack.append(i)\n",
    "        return max([(right[i]-left[i]-1)*heights[i] for i in range(n)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        def do(heights):\n",
    "            if len(heights) == 1:\n",
    "                return heights[0]\n",
    "            q = [[0, heights[0]]]\n",
    "            res = heights[0]\n",
    "            for i, h in enumerate(heights):\n",
    "                if i == 0:\n",
    "                    continue\n",
    "                if len(q) == 0 or h >= q[-1][1]:\n",
    "                    q.append([i, h])\n",
    "                else:\n",
    "                    while len(q)>0 and h < q[-1][1]:\n",
    "                        start, starth = q.pop()\n",
    "                        if len(q) > 0:\n",
    "                            end = q[-1][0]\n",
    "                        else:\n",
    "                            end = -1\n",
    "                        res = max(res, starth * (i - end - 1))\n",
    "                    q.append([i, h])\n",
    "            if len(q) > 0:\n",
    "                end = len(heights)\n",
    "                for i, x in enumerate(q):\n",
    "                    c, ch = x\n",
    "                    if i == 0:\n",
    "                        res = max(res, q[0][1] * end)\n",
    "                    else:\n",
    "                        res = max(res, ch * (end - q[i-1][0]-1))    \n",
    "            return res\n",
    "        return do(heights)\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        ansr = [1] * len(heights)\n",
    "        ansl = [1] * len(heights)\n",
    "\n",
    "        stackr = []\n",
    "        heights.append(-1)\n",
    "        for idx in range(len(heights)):\n",
    "            while stackr  and heights[stackr[-1]] > heights[idx]:\n",
    "                aa = stackr.pop()\n",
    "                ansr[aa] = idx - aa\n",
    "            \n",
    "            stackr.append(idx)\n",
    "            # print(stackr, ansr)\n",
    "        stackl = []\n",
    "        heights.pop()\n",
    "        tmp = heights\n",
    "        heights = [-1]\n",
    "        heights.extend(tmp)\n",
    "        for idx in range(len(heights) - 1, -1, -1):\n",
    "            while stackl and heights[stackl[-1]] > heights[idx]:\n",
    "                aa = stackl.pop()\n",
    "                \n",
    "                ansl[aa - 1] = aa - idx\n",
    "            stackl.append(idx)\n",
    "        print(ansr)\n",
    "        print(ansl)\n",
    "        for i in range(len(ansr)):\n",
    "            ansr[i] = heights[i + 1] * (ansl[i] + ansr[i] - 1)\n",
    "        return max(ansr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        显然的单调栈应用\n",
    "        \"\"\"\n",
    "        ans = 0\n",
    "\n",
    "        stk = []\n",
    "        for i, height in enumerate(heights):\n",
    "            pw = 0  # 当前位置之前的宽度\n",
    "            while stk and heights[stk[-1][0]] > height:\n",
    "                j, w = stk.pop()\n",
    "                pw += w+1\n",
    "                ans = max(ans, heights[j]*(i-j+w))\n",
    "            stk.append((i, pw))\n",
    "\n",
    "        for i, w in stk:\n",
    "            h = heights[i]\n",
    "            ans = max(ans, h*(stk[-1][0] - i + 1 + w))\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        arr = [0] + heights + [0]\n",
    "        ans, stack = 0, []\n",
    "        for index, v in enumerate(arr):\n",
    "            while stack and v < stack[-1][1]:\n",
    "                index_, v_ = stack.pop()\n",
    "                ans = max(ans, v_*(index-stack[-1][0]-1))\n",
    "            stack.append((index, v))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        heights.append(0)\n",
    "        stack = deque()\n",
    "        stack.append((0,-1))\n",
    "        maximum = 0\n",
    "        for i in range(len(heights)):\n",
    "            while stack and stack[-1][0] > heights[i]:\n",
    "                maximum = max(maximum, stack[-1][0] * (i - stack[-2][1] - 1))\n",
    "                stack.pop()  \n",
    "            stack.append((heights[i],i))\n",
    "\n",
    "        return maximum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        stack = [(-1, -1)]\n",
    "        result = 0\n",
    "        index = 0\n",
    "        for index, height in enumerate(heights):\n",
    "            while height < stack[-1][0]:\n",
    "                result = max(result, (index - stack[-2][1] - 1) * (stack[-1][0]))\n",
    "                stack.pop()\n",
    "            stack.append((height, index))\n",
    "        while stack[-1][0] != -1:\n",
    "            result = max(result, (index + 1 - stack[-2][1] - 1) * (stack[-1][0]))\n",
    "            stack.pop()\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        ans = 0\n",
    "        s = [(-1, 0)]\n",
    "        for i, h in enumerate(heights + [0]):\n",
    "            while s[-1][1] > h:\n",
    "                _, prev_h = s.pop()\n",
    "                area_i = (i-s[-1][0]-1) * prev_h\n",
    "                ans = max(ans, area_i)\n",
    "            \n",
    "            s.append((i, h))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        if n == 1:\n",
    "            return heights[0]\n",
    "        arr = [0] + heights + [0]\n",
    "        ans, stack = 0, []\n",
    "        for index, item in enumerate(arr):\n",
    "            while stack and item < stack[-1][1]:\n",
    "                _, _v = stack.pop()\n",
    "                ans = max(ans, _v*(index-stack[-1][0] - 1))\n",
    "            stack.append((index, item))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        heights = [0] + heights + [0]\n",
    "\n",
    "        stack = []\n",
    "        max_size = 0\n",
    "        for i, height in enumerate(heights):\n",
    "            if not stack:\n",
    "                stack.append([i, height])\n",
    "                continue\n",
    "            if stack[-1][1] > height:\n",
    "                while stack[-1][1] > height:\n",
    "                    p = stack.pop()\n",
    "                    cur_size = p[1] * (i-stack[-1][0]-1)\n",
    "                    max_size = max(max_size, cur_size)\n",
    "                stack.append([i,height])\n",
    "            else:\n",
    "                stack.append([i, height])\n",
    "        return max_size"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        n = len(heights)\n",
    "        right = [n] * n\n",
    "        queue = []\n",
    "        for i, h in enumerate(heights):\n",
    "            while queue and queue[-1][0] > h:\n",
    "                curh, curi = queue.pop()\n",
    "                right[curi] = i\n",
    "            queue.append([h, i])\n",
    "        left = [-1] * n\n",
    "        queue = []\n",
    "        for j in range(n - 1, -1, -1):\n",
    "            h = heights[j]\n",
    "            while queue and queue[-1][0] > h:\n",
    "                curh, curj = queue.pop()\n",
    "                left[curj] = j\n",
    "            queue.append([h, j])\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            lefti = left[i]\n",
    "            righti = right[i]\n",
    "            cur = heights[i] + (i - lefti - 1) * heights[i] + (right[i] - i - 1) * heights[i]\n",
    "            ans = max(cur, ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        res = 0\n",
    "        heights.append(0)\n",
    "        stack = []\n",
    "        for idx, h in enumerate(heights):\n",
    "            last_idx = idx\n",
    "            while stack and stack[-1][0] > h:\n",
    "                last_h, last_idx = stack.pop()\n",
    "                res = max(res, last_h * (idx - last_idx))\n",
    "            stack.append([h, last_idx])\n",
    "            # print(stack, idx, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        heights = [0] + heights + [0]\n",
    "        ans, stack = 0, [] # (idx, height)\n",
    "\n",
    "        for idx, height in enumerate(heights):\n",
    "            while stack and height < stack[-1][1]:\n",
    "                pre_idx, pre_height = stack.pop()\n",
    "                ans = max(ans, (idx - stack[-1][0] - 1) * pre_height) # 新遍历到的，与再前一个，夹逼一下\n",
    "            stack.append((idx, height))\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        heights = [0] + heights + [0]\n",
    "        ans, stack = 0, [] # (idx, height)\n",
    "\n",
    "        for idx, height in enumerate(heights):\n",
    "            while stack and height < stack[-1][1]:\n",
    "                pre_idx, pre_height = stack.pop()\n",
    "                ans = max(ans, (idx - stack[-1][0] - 1) * pre_height) # 新遍历到的，与再前一个，夹逼一下\n",
    "            stack.append((idx, height))\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        stack = [(0, -1)]\n",
    "        heights.append(0)\n",
    "        res = 0\n",
    "        for i,height in enumerate(heights):\n",
    "            while stack and height < stack[-1][0]:\n",
    "                h = stack[-1][0]            # 长\n",
    "                w = i - stack[-2][1] - 1    # 宽\n",
    "                res = max(res, h*w)\n",
    "                stack.pop()                 # 栈顶元素已经求过面积，pop出来，换下一个元素\n",
    "            stack.append((height, i))       # 和栈顶元素比较之后，当前元素才可以入栈\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        stack = [(-1, 0)]\n",
    "        heights.append(0)\n",
    "        res = 0\n",
    "        for i,height in enumerate(heights):\n",
    "            while stack and height < stack[-1][1]:\n",
    "                h = stack[-1][1]            # 长\n",
    "                w = i - stack[-2][0] - 1    # 宽\n",
    "                res = max(res, h*w)\n",
    "                stack.pop()                 # 栈顶元素已经求过面积，pop出来，换下一个元素\n",
    "            stack.append((i, height))       # 和栈顶元素比较之后，当前元素才可以入栈\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        stack = [(0, -1)]\n",
    "        heights.append(0)\n",
    "        res = 0\n",
    "        for i,height in enumerate(heights):\n",
    "            while stack and height < stack[-1][0]:\n",
    "                h = stack[-1][0]            # 长\n",
    "                w = i - stack[-2][1] - 1    # 宽\n",
    "                res = max(res, h*w)\n",
    "                stack.pop()                 # 栈顶元素已经求过面积，pop出来，换下一个元素\n",
    "            stack.append((height, i))       # 和栈顶元素比较之后，当前元素才可以入栈\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sortedcontainers\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        l = sorted((h, p) for p, h in enumerate(heights))\n",
    "        place = sortedcontainers.SortedList([-1, len(heights)])\n",
    "        res = 0\n",
    "        for h, p in l:\n",
    "            p1 = place.bisect(p)\n",
    "            res = max(res, h*(place[p1]-place[p1-1]-1) )\n",
    "            place.add(p)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        heights = [-1]+heights+[-1]\n",
    "        n = len(heights)\n",
    "        left, right = [0]*n, [0]*n\n",
    "        stackl, stackr = [], []\n",
    "        for i in range(n):\n",
    "            while stackr and heights[stackr[-1]]>heights[i]:\n",
    "                tmpr = stackr.pop()\n",
    "                right[tmpr] = i-tmpr\n",
    "            while stackl and heights[stackl[-1]]>heights[n-i-1]:\n",
    "                tmpl = stackl.pop()\n",
    "                left[tmpl] = tmpl-(n-i-1)\n",
    "            stackr.append(i)\n",
    "            stackl.append(n-i-1)\n",
    "        res = 0\n",
    "        # print(left,right)\n",
    "        for i in range(1,n-1):\n",
    "            res = max(res,(right[i]+left[i]-1)*heights[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        stack = []\n",
    "        heights = [0] + heights + [0]\n",
    "        left = [0] * len(heights)\n",
    "        for i in range(len(heights)):\n",
    "            if not stack:\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                if heights[i] >= heights[stack[-1]]:\n",
    "                    stack.append(i)\n",
    "                else:\n",
    "                    while stack and heights[i] < heights[stack[-1]]:\n",
    "                        prev = stack.pop()\n",
    "                        left[prev] = i - prev\n",
    "                    stack.append(i)\n",
    "        right = [0] * len(heights)\n",
    "        for i in range(len(heights)-1, -1, -1):\n",
    "            if not stack:\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                if heights[i] >= heights[stack[-1]]:\n",
    "                    stack.append(i)\n",
    "                else:\n",
    "                    while stack and heights[i] < heights[stack[-1]]:\n",
    "                        prev = stack.pop()\n",
    "                        right[prev] = prev - i\n",
    "                    stack.append(i)\n",
    "        max_area = 0\n",
    "        for i in range(1, len(heights)-1):\n",
    "            width = right[i] + left[i] - 1\n",
    "            max_area = max(max_area, width * heights[i])\n",
    "        return max_area\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        heights = heights + [0]\n",
    "        stk = []\n",
    "        stk.append([0, 0])\n",
    "        res = 0\n",
    "        for i, val in enumerate(heights, 1): #(index, val) \n",
    "            while val < stk[-1][1]:\n",
    "                cur = stk.pop()\n",
    "                area = cur[1] * (i - stk[-1][0] - 1)\n",
    "                res = max(res, area)\n",
    "            stk.append([i, val])\n",
    "        return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
